package oj.hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 合并区间 {
    public int[][] merge(int[][] intervals) {
        //先按左端点排序
        Arrays.sort(intervals,(v1, v2)->{
            return v1[0]-v2[0];
        });
        List<int[]> ret = new ArrayList<>();
        int left = intervals[0][0],right = intervals[0][1];
        for(int i = 1;i < intervals.length;i++) {
            int a = intervals[i][0],b = intervals[i][1];
            if(a <= right) {
                //重叠, 合并
                right = Math.max(right,b);
            }else {
                //不重叠,将当前区间加入到ret中并更新
                ret.add(new int[]{left,right});
                left = a;
                right = b;
            }
        }
        //将最后一个[left,right]加入到ret中
        ret.add(new int[]{left,right});
        return ret.toArray(new int[ret.size()][]);
    }
}
